"""
11月15日百度现场面试算法题
"""

def quick_sort(l1):
    """第1题，快速排序。时间复杂度O(nlgn)"""

    # 长度为0或者1，就不用再分割了
    if len(l1) < 2:
        return l1

    # 参照点统一选择第一个元素
    pivot = l1[0]

    # 小的放在左边，大的放在右边
    less = [i for i in l1[1:] if i < pivot]
    greater = [i for i in l1[1:] if i > pivot]

    # 递归分治
    return quick_sort(less) + [pivot] +  quick_sort(greater)


def merge(left, right):
    """合并两个已排序好的列表，产生一个新的已排序好的列表"""
    result = []  # 新的已排序好的列表
    i = 0  # 下标
    j = 0
    # 对两个列表中的元素 两两对比。
    # 将最小的元素，放到result中，并对当前列表下标加1
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result


def merge_sort(seq):
    """二路归并排序"""

    if len(seq) <= 1:
        return seq

    # 将列表分成更小的两个列表
    mid = len(seq) // 2

    # 分别对左右两个列表进行处理，分别返回两个排序好的列表
    left = merge_sort(seq[:mid])
    right = merge_sort(seq[mid:])

    # 对排序好的两个列表合并，产生一个新的排序好的列表
    return merge(left, right)


a = [23,33,44,12,55,12,8]
print(merge_sort(a))


# if __name__ == '__main__':
#     a = yh_digui(7)
#     print('-'*10 + '第1题' + '-'*10)
#     print(a)
#
#     li1 = [6, 9, 18, 33, 34, 89, 90, 93, 2000, 2001]
#     k = 2000
#     p = search_2fen(li1, k)
#     print('-'*10 + '第2题' + '-'*10)
#     print(p)
